package array;

import java.math.BigInteger;
import java.util.*;

public class Njuzhen {
    public static void main(String[] args) {
        int[] arr = {0};
        for (int a:plusOne(arr)){
            System.out.print(a);
            System.out.println("change");
        }
    }

    //数字按位保存在数组中，对其最后一位加一，返回结果数组
    public static int[] plusOne (int[] arr) {
        // write code here
        int len = arr.length;
        if(len==0){
            return arr;
        }
        int value = 0;
        for(int a=len-1;a>-1;a--){
            int res  = arr[a] + value ;
            if (a==len-1){
                res+=1;
            }
            value = 0;
            if(res>9){
                res-=10;
                value = 1;
            }
            arr[a] = res;
        }
        if(value!=1){
            return arr;
        }
        int[] ar = new int[len+1];
        ar[0]=1;
        for(int a=1;a<=len;a++){
            ar[a] = arr[a-1];
        }
        return ar;
    }

    //数组中所有数字都只出现了两次，只有两个数字出现了一次，返回这两个数字
    //愚蠢办法：使用hashmap统计出现次数
    public static int getTwice(int[] arr){
        //假设出现一次的数字只有一个  方案如下：
        ArrayList<Integer> list = new ArrayList<>();
        int sumAll = 0;
        int sumNotRepeat = 0;
        for (int x:arr){
            if (!list.contains(x)){
                list.add(x);
                sumNotRepeat+=x;
            }
            sumAll+=x;
        }
        return (sumNotRepeat*3-sumAll)/2;
    }

    //最大子数组和   初步：两次遍历求解    进阶：贪心算法
    public static int maxSubArraySum(int[] arr){
        //贪心算法:如果累加的和小于0，则丢弃,记录每次累加后的最大值
        //-1,8,3,-2,5,-3,6,-8
        int ans = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=0; i<arr.length; i++)
        {
            sum += arr[i];
            if(sum > ans)
            {
                ans = sum;
            }
            if(sum < 0)
            {
                sum = 0;   //子串和为负数，丢掉
            }
        }
        return ans;
        /*
        :遍历算法
        int res = Integer.MIN_VALUE;
        for (int a=0;a<arr.length;a++){
            int tempmax = Integer.MIN_VALUE;
            int sum = 0;
            for (int b=a;b<arr.length;b++){
                sum+=arr[b];
                tempmax = Math.max(tempmax,sum);
            }
            res = Math.max(res,tempmax);
        }
        return res;
         */
    }




    //分解因子仅为3 5 7的数，求第k个数
    //最初：遍历  直到凑够k个满足条件的数字
    //进阶 采用构造法，从头到位构造  效率更高 ，不需要再去对每一个数字进行判断
    public static int getK(int k){
        int a=3,b=5,c=7;
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(a);
        arr.add(b);
        arr.add(c);
        for (int x=0;x<k;x++){
            if (!arr.contains(arr.get(x)*3)){
                arr.add(arr.get(x)*3);
            }
            if (!arr.contains(arr.get(x)*5)){
                arr.add(arr.get(x)*5);
            }
            if (!arr.contains(arr.get(x)*7)){
                arr.add(arr.get(x)*7);
            }
        }
        Collections.sort(arr);
        return arr.get(k-1);
    }





    public static int minInsertions (String s) {
        // write code here
        int i = 0;
        int resNum = 0;
        int r = 0,l=0;
        int temp = 0;
        for (i=0;i<s.length();i++){
            if (s.charAt(i) == '('){
                l++;
            }else{
                temp = 1;
                if (i+1 <s.length() && s.charAt(i+1) == ')'){
                    i++;
                    temp = 2;
                }
                if (temp == 1 ){
                    resNum++;
                }
                r+=2;
            }
            if (r>l*2){
                resNum++;
                l++;
            }
        }
        resNum +=(l*2 - r);
        return resNum;
    }



    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> p = new PriorityQueue<>();
        for (int a:arr){
            p.add(a);
        }
        int[] res = new int[k];
        for (int a=0;a<k;a++){
            res[a] = p.poll();
        }
        return res;
    }

    public static int GetMaxConsecutiveOnes (int[] arr, int k) {
        // write code here
        int maxLen = -1;
        for (int a=0;a<arr.length;a++){
            int tempLen = 0;
            int tk = k;
            for (int b=a;b<arr.length;b++){
                if (arr[b] == 1){
                    tempLen++;
                }else if (arr[b]==0 &&tk>0){
                    tempLen++;
                    tk--;
                }else if (arr[b]==0 &&tk<=0){
                    break;
                }
            }
            maxLen = Math.max(maxLen,tempLen);
        }
        return maxLen;
    }




    public static int[] SpiralMatrix (int[][] matrix) {
        // write code here
        // a:起始行  b:终止列  c：终止行   d：起始列
        ArrayList<Integer> arrayList = printByRows(matrix,0,matrix[0].length-1,matrix.length-1,0);
        int[] res = new int[arrayList.size()];
        for (int a=0;a<res.length;a++){
            res[a] = arrayList.get(a);
        }
        return res;
    }


    //维护可以跳到的最远位置 核心思想，如果一个位置可以到达 那么这个位置的左侧位置都可以到达
    public boolean canJump(int[] nums) {
        int max = 0;
        for (int a=0;a<max;a++){
            if (max == nums.length || a==nums.length){
                return true;
            }
            if (nums[a]+a>max){
                max = nums[a]+a;
            }
        }
        return false;
    }


    public static ArrayList<Integer> printByRows(int[][] arr,int a,int b,int c,int d){
        //1 2 1 1
        ArrayList<Integer> list = new ArrayList<>();
        if(a>c || d>b){
            return list;
        }

        if (b-d==0){
            while (a<=c){
                list.add(arr[a][b]);
                a++;
            }
            return list;
        }
        if (a-c==0){
            while (d<=b){
                list.add(arr[a][d]);
                d++;
            }
            return list;
        }
        int a1= d;
        while(a1<=b){
            list.add(arr[a][a1]);
            a1++;
        }

        int b1 = a+1;
        while(b1<=c){
            list.add(arr[b1][b]);
            b1++;
        }
        int c1 = b-1;
        while(c1>=d){
            list.add(arr[c][c1]);
            c1--;
        }

        int d1 = c-1;
        while(d1>=a+1){
            list.add(arr[d1][d]);
            d1--;
        }
        list.addAll(printByRows(arr,a+1,b-1,c-1,d+1));
        return list;
    }



    /*
    * 输入两个整数序列，第一个序列表示栈的压入顺序，
    * 请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
    * 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
    * 但4,3,5,1,2就不可能是该压栈序列的弹出序列。
    * */
    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int a= 1,b=0;
        stack.add(pushA[0]);
        while (!stack.isEmpty()){
            if (popA[b] != stack.peek()){
                if (a>pushA.length-1){
                    return false;
                }
                stack.push(pushA[a]);
                a++;
            }else {
                stack.pop();
                b++;
            }
        }
        return true;
    }


    public static int cutRopeWithDP(int target) {
        int[] arr= new int[target+1];
        arr[1] = 1;
        arr[0] = 1;
        int max = 0;
        for (int a=2;a<=target;a++){
            arr[a] = a;
            for (int b = 1;b<a;b++){
                arr[a] =Math.max(arr[a], b * arr[a-b]);
            }
        }
        return arr[target];
    }


    //切割绳子
    public static int cutRope(int target) {
        if (target==1){  //递归跳出条件
            return 1;
        }
        int max = target;  //最大乘积必须大于等于绳子未切割的长度，比如长度为3时 1*2=2 小于3，不符合条件
        for (int a=1;a<target;a++){  //依次选取不同长度的第一段 求最大乘积即可
            max = Math.max(max,a*cutRope(target-a));
        }
        return max;
    }



    //有一个数  在数组中出现次数超过数组长度的一半  请输出
    public static int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int a:array){
            int value = 1;
            if (map.containsKey(a)){
                value += map.get(a);
            }
            map.put(a,value);
        }
        Iterator<Integer> it = map.keySet().iterator();
        int res = 0;
        int resNum = 0;
        while (it.hasNext()){
            res = it.next();
            resNum = map.get(res);
            if (resNum >= (array.length/2+array.length%2)){
                return  res;
            }
        }
        return -1;
    }



    //给定一个数组，返回连续区间最大和
    public static int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        int res=Integer.MIN_VALUE;

        for(int a = 0;a<len;a++){
            int max1 = Integer.MIN_VALUE;
            int max2 = 0;
            for(int b = a;b<len;b++){
                max2 = max2+array[b];
                max1 = Math.max(max1,max2);
            }
            res = Math.max(res,max1);
        }
        return res;
    }
    /*
     *给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
     *如果数组元素个数小于 2，则返回 0
     * */
    public int maximumGap(int[] nums) {
        if (nums.length <2){
            return 0;
        }
        Arrays.sort(nums);
        int min = Integer.MIN_VALUE;
        for (int a=0;a<nums.length-1;a++){
            int res= Math.abs(nums[a] - nums[a+1]);
            min = min< res ? res :min;
        }
        return min;
    }

    /*
   * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
   * */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length+nums2.length;
        int p1= 0;
        int p2= 0;
        int[] arr = new int[(len/2)+1];  //3
        for (int a =0;a<arr.length;a++){
            int t1=Integer.MAX_VALUE;
            if (p1<nums1.length){
                t1=nums1[p1];
            }
            int t2=Integer.MAX_VALUE;
            if (p2<nums2.length){
                t2=nums2[p2];
            }

            if (t2<t1) {
                arr[a] = t2;
                p2++;
            } else {
                arr[a] = t1;
                p1++;
            }
        }
        if (len%2==0){
            return ((double)arr[arr.length-1]+(double)arr[arr.length-2])/2;
        }
        return (double)arr[arr.length-1];
    }


    /*
     * 找出输入数组中最小的k个数组 返回一个集合
     * */
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> max = new PriorityQueue<>();//默认小根堆，大根堆需要重新构造
        for (int a: input){
            max.add(a);
        }
        ArrayList<Integer> resArr = new ArrayList<>();
        int a = 0;
        while (a<=k){
            resArr.add(max.poll());
        }
        return resArr;
    }
}